package Top_Interview_Questions.Tree;

import Top_Interview_Questions.Tree.Supple.Node;
import Top_Interview_Questions.Tree.Supple.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/9 12:49
 * <p>
 * https://www.cnblogs.com/Demrystv/p/9043356.html
 * https://www.cnblogs.com/xiaolovewei/p/7763867.html
 * 树的几种遍历
 *
 * 这题手画个图就很好理解了
 */
public class _0116 {

    public static void main(String[] args) {
        _0116 test = new _0116();

        Node root = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        Node node5 = new Node(6);
        Node node6 = new Node(7);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;

        test.connect2(root);
    }

    /*-------------------------------------------迭代-----------------------------------------*/
    public Node connect2(Node root) {
        if (root == null) {
            return root;
        }
        Node pre = root;
        Node cur = null;
        Node start = pre;
        while (pre.left != null) {
            //遍历到了最右边的节点，要将 pre 和 cur 更新到下一层，并且用 start 记录
            if (cur == null) { //cur==null就是遍历到了下一层
                //我们只需要把 pre 的左孩子的 next 指向右孩子。
                pre.left.next = pre.right;

                pre = start.left;
                cur = start.right;
                start = pre;
                //将下一层的 next 连起来，同时 pre、next 后移
            } else {
                //把 pre 的左孩子的 next 指向右孩子
                pre.left.next = pre.right;
                //pre 的右孩子的 next 指向 cur 的左孩子。
                pre.right.next = cur.left;

                pre = pre.next;
                cur = cur.next;
            }
        }
        return root;
    }
    /*----------------------------------------------------------------------------------------*/

    /**
     *       1
     *     /   \
     *    2     3
     *   / \   / \
     *  4  5  6  7
     */

    /*-------------------------------------层次遍历的解法---------------------------------------*/

    public Node connect1(Node root) {
        if (root == null)
            return root;

        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node pre = null;
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                //从第二个节点开始，将前一个节点的 pre 指向当前节点
                if (i > 0)
                    pre.next = cur;
                pre = cur;
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
        return root;
    }
    /*----------------------------------------------------------------------------------------*/



}
